package ch3.part1;

/**
 * 根据 BySocket 的公众号推文实现
 * 链接：https://mp.weixin.qq.com/s/bh2PIraXF_Uh9YtEfhSeLQ
 * 本类中并没有涉及到二叉树的自平衡
 *
 * @author liuwanxiang
 * @version 2019-5-17
 */
public class BinarySearchTree {

    /**
     * 根节点
     */
    private TreeNode root;

    /**
     * 查找 key 值对应的二叉树节点
     */
    TreeNode search(int key) {
        TreeNode current = root;
        while (current != null && key != current.value) {
            if (key < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current;
    }

    /**
     * 插入 key 值，并返回树节点
     */
    TreeNode insert(int key) {
        // 新增节点
        TreeNode newNode = new TreeNode(key);
        // 当前节点
        TreeNode current = root;
        // 上个节点
        TreeNode parent;

        // 如果根节点为空
        if (current == null) {
            root = newNode;
            return newNode;
        }

        while (true) {
            parent = current;
            if (key < current.value) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return newNode;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return newNode;
                }
            }
        }
    }

    /**
     * 删除节点
     */
    TreeNode delete(int key) {
        TreeNode parent = root;
        TreeNode current = root;
        boolean isLeftChild = false;

        // 找到删除节点 及 是否在左子树
        while (current.value != key) {
            parent = current;
            if (current.value > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return current;
            }
        }

        if (current.left == null && current.right == null) {
            // 如果删除节点左节点为空 , 右节点也为空
            // 即该节点为叶子节点，直接删除，父节点的左（右）节点置空即可
            if (current == root) {
                root = null;
            }
            // 在左子树
            if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (current.right == null) {
            // 如果删除节点只有一个左侧子节点
            // 左侧子节点代替删除节点即可
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            // 如果删除节点只有一个右侧子节点
            // 右侧子节点代替删除节点即可
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else {
            // 如果删除节点左右子节点都不为空
            // 找到删除节点的后继者
            TreeNode successor = getDeleteSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return current;
    }

    /**
     * 获取删除节点的后继者
     * <p>
     * 删除节点的后继者是在其右节点树种最小的节点
     */
    private TreeNode getDeleteSuccessor(TreeNode deleteNode) {

        // 后继者
        TreeNode successor = null;
        TreeNode successorParent = null;
        TreeNode current = deleteNode.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 检查后继者(不可能有左节点树)是否有右节点树
        // 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.
        if (successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }
        return successor;
    }

    /**
     * 给定 root 节点，打印该节点向下的子树信息
     * 前序遍历的递归实现，根左右
     */
    static void toString(TreeNode root) {
        if (root != null) {
            System.out.print("value = " + root.value + " -> ");
            toString(root.left);
            toString(root.right);
        }
    }

    /**
     * 确定二叉树的最大深度或者最小深度
     * 实例方法
     */
    int maxDepth() {
        return getMaxDepth(root);
    }

    int minDepth() {
        return getMinDepth(root);
    }

    /**
     * 确定二叉树的最大深度
     * 递归实现，node为空，深度为0；node不为空，继续递归
     */
    static int getMaxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = getMaxDepth(node.left);
        int right = getMaxDepth(node.right);
        return Math.max(left, right) + 1;
    }

    static int getMinDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getMin(root);
    }

    /**
     * 确定二叉树的最小深度
     * 递归实现，node为空，深度为MAX_INT；node没有子节点，深度为1；
     * 存在左侧或右侧节点时，继续递归，二者取最小值
     */
    private static int getMin(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return Math.min(getMin(root.left), getMin(root.right)) + 1;
    }

    boolean isBalanced() {
        return isBalanced(root);
    }

    static boolean isBalanced(TreeNode root) {
        return maxDepth2(root) != -1;
    }

    private static int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = maxDepth2(root.left);
        int right = maxDepth2(root.right);
        if (left == -1 || right == -1 || left - right > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }

    /**
     * 二叉树的节点
     */
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        private TreeNode(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }

}